Complete Linux

home *** CD-ROM | disk | FTP | other *** search

/ Complete Linux / Complete Linux.iso / docs / apps / database / postgres / postgre2.z / postgre2 / doc / implementation / query-tree.me < prev

Wrap

Text File | 1992-08-27 | 27.8 KB | 860 lines

.\"---------------------------------------------------------------------- .\" FILE .\" query-tree.t .\" .\" DESCRIPTION .\" Specification for the query (parser => planner) and plan .\" (planner => executor) trees .\" .\" RCS ID .\" $Header: /private/postgres/doc/implementation/RCS/query-tree.me,v 1.1 1990/07/30 13:50:41 kemnitz Exp $ .\"---------------------------------------------------------------------- .ds ar <\\(em\\(em .nr pp 11 .nr sp 12 .nr tp 12 .nr fp 10 .ll 6.5i .(l C .sz \n(sp .ft B QUERY TREE / QUERY PLAN SPECIFICATION (Printed: \*(td) .ft R .)l .sp .sz \n(pp .sp For notational purposes, anything appearing in italics is defined elsewhere in this document. Anything in bold face surrounded by quotes appears explicitly within a runtime query tree/plan as a LISP string. Anything appearing as a list is represented literally as a LISP list. [] indicates something that is optional; {} indicates 0 or more. .sp .he 'Query Tree / Query Plan Specification''%' .sh 1 "Query Tree Representation" .sp The parser will produce the following query tree for each query that requires optimization: .(l (\fIRoot TargetList Qualification\fR) .)l Each of the above three components is a list containing further information. .sh 2 "Root" .sp \fBRoot\fR looks like: .(l (\fINumLevels CommandType ResultRelation RangeTable Priority RuleInfo\fR) .)l This list contains information required by the planner as well as the executor. The planner itself does not modify any of these elements, although some of its preprocessing routines may change portions of root before it is seen by the executor. .sh 3 "NumLevels" .sp \fBNumLevels\fR indicates the maximum attribute nesting in a query. That is, it indicates the maximum number of \*(lqnested dot\*(rq fields found in any variable in that query. For example, a query without range variables such as .(l retrieve (x = 1 + 2) .)l will have \fBNumLevels\fR = 0, a query such as .(l retrieve (pinhead.name) where pinhead.saying = "Yow!!!" .)l that contains normal range variables will have \fBNumLevels\fR = 1, a query such as .(l retrieve (sorority.all) where sorority.members.name = "Marti" .)l will have \fBNumLevels\fR = 2, and so on. .sh 3 "CommandType" .sp \fBCommandType\fR indicates what kind of query is being executed. \fBCommandType\fR will be a single symbol from: .(l retrieve append replace delete .)l (other POSTQUEL commands are not optimized, so the planner should never see them). .sh 3 "ResultRelation" .sp \fBResultRelation\fR specifies the target relation of a \*(lqretrieve\*(rq or the update relation for \*(lqappend\*(rq, \*(lqreplace\*(rq, and \*(lqdelete\*(rq. It may take one of three forms: .np If the query is a \*(lqretrieve\*(rq and no result relation is specified, then \fBResultRelation\fR is nil. .np If the query is a \*(lqretrieve into\*(rq, then \fBResultRelation\fR is a list containing a string representing the result relation's name and a string from: .(l \fB\*(lqHEAVY\*(rq \*(lqLIGHT\*(rq \*(lqNONE\*(rq\fR .)l which represents the level of archiving which has been specified for the result relation. .np If the query is an update, \fBResultRelation\fR will always be the index into the \fIrangetable\fR corresponding to the relation to be updated. .sh 3 "RangeTable" .sp \fBRangeTable\fR is a list containing a \fIrangetable entry\fR for each instance of a relation (i.e., range variable) in a query. Every \fIrelid\fR and \fIvarno\fR within the query tree, and almost every one within the resulting query plan, is an integer index within the query's rangetable. This index is 1-based (e.g., var nodes that refer to the first relation in the rangetable are given varno ``1''). .sp A rangetable entry looks like: .(l ( \fIRelationName RelationOID TimeRange Flags RuleLocks\fR ) .)l \fBRelationName\fR is a string corresponding to the relation's catalog name, \fBRelationOID\fR is an integer corresponding to the OID of the RELATION relation tuple that describes the given relation, \fBTimeRange\fR is an internal structure that describes the historical time span over which this rangetable entry is valid, \fBFlags\fR is a list of zero or more symbols from: .(l archive inheritance union version .)l that specifies special treatment from the planner, and \fBRuleLocks\fR holds the rule lock information for that relation (since this is generated by a planner preprocessor, the parser simply puts nil here). In the case of archival, inheritance, union and version queries, the planner generates an \fBAPPEND\fR query plan node (see below) that contains a set of rangetable entries which must be substituted in turn for this rangetable entry, as well as separate query plans to be executed. .sh 3 "Priority" .sp \fBPriority\fR is simply an integer from 0..7 that indicates the query priority. Only rule plans can have priorities greater than 0. .sh 3 "RuleInfo" .sp If the query is part of a \*(lqdefine rule\*(rq query, \fBRuleInfo\fR is a containing a \fIrule identifier\fR and exactly one symbol from: .(l always once never .)l The rule identifier is an object identifier from the RULE relation; the symbol is the tag associated with the rule definition. For example, \fBRuleInfo\fR might look like: .(l ( 387457893 always ) .)l The rule identifier will be filled in by a traffic cop or planner preprocessor routine. For all other queries, \fBRuleInfo\fR is nil. .sh 2 "TargetList" .sp A targetlist describes the structure of a tuple and consists of a list of (\fIresdom expr\fR) pairs, one for each attribute in the tuple to be constructed. A \fBresdom\fR (result domain) node contains information about the attribute, and an \fBexpr\fR (expression) describes how to set the value of the attribute. .sp The initial targetlist from the query tree describes what the final result tuples should look like (targetlists are also used in query plans to describe intermediate results such as scan projections, join results, and temporaries). In the case of the delete command, the initial targetlist is always nil. For the other update queries, the planner's preprocessor fills in any missing attributes that the user has not specified, either with constants corresponding to the default values of the missing attributes\** .(f \** If no default value exists for an attribute type, the attribute will have a null value. .)f (for \*(lqappend\*(rq) or with variables corresponding to the unchanged attributes of a tuple (for \*(lqreplace\*(rq). .sp The structure of the \fBresdom\fR node is described below; an \fBexpr\fR can consist of a combination of nodes: .(l \fIexpr\fR = \fIvar\fR | \fIconst\fR | \fIparam\fR | (\fIoper expr\fR [\fIexpr\fR]) | (\fIfunc\fR {\fIexpr\fR}) .)l .sp The structures of the different nodes in an expr are described below, but the function of the nodes may be briefly summarized as: .nr zz \n(ii .nr ii 6m .sp .ip \fIvar\fR Refer to some relation attribute entry which corresponds to the target list entry (i.e., the contents of a relation's tuple). .ip \fIconst\fR Constant values. .ip \fIparam\fR Used as parameters \(em placeholders for constants \(em within a query. The planner treats them as if they are constants of unknown value (i.e., null constants) for optimization purposes. .ip \fIoper\fR Describes the system- or user-defined unary or binary operator that will be applied to the argument exprs to produce a new value. .ip \fIfunc\fR Correspond to calls to system- or user-defined functions, which may have zero or more arguments. .nr ii \n(zz .lp Example: ((\fIresdom var\fR) (\fIresdom\fR (\fIoper var var\fR))) .br is a targetlist with two attributes, where the second element involves a computation between two tuple attributes. .sh 2 "Qualification" .sp A qualification consists of restriction and join clauses which are evaluated before the final result is returned. .sp The qualifications produced by the parser are not normalized in any way. That is, the parsed qualification will be an arbitrary boolean expression: .(l \fIqualification\fR = ({\fIqual\fR}) \fIqual\fR = \fIexpr\fR | (\*(lq\fBNOT\fR\*(rq \fIqual\fR) | (\*(lq\fBOR\fR\*(rq \fIqual \fR{\fIqual\fR}) | (\*(lq\fBAND\fR\*(rq \fIqual \fR{\fIqual\fR}) .)l .sp The qualification supplied to the planner must be normalized in certain ways.\** .(f \** This normalization occurs in yet another preprocessing module. .)f A qualification must be specified in conjunctive normal form. Furthermore, if it is at all possible, all \*(lqnot\*(rqs are removed and all variables are placed on the left hand side of the clause operator. If it is not possible to remove a \*(lqnot\*(rq (perhaps because a negator is unavailable), then the \*(lqnot\*(rq must be pushed to the innermost comparison, e.g., \*(lq(not ((a = b) and (c = d)))\*(rq might become \*(lq(not (a = b) or not (c = d))\*(rq if the operator \*(lq!=\*(rq does not exist for the appropriate types. .sp A qualification as seen by the planner is: .(l \fIqualification\fR = ({\fIqual\fR | \fIorqual\fR}) \fIqual\fR = \fIexpr\fR | (\*(lq\fBNOT\fR\*(rq \fIexpr\fR) \fIorqual\fR = (\*(lq\fBOR\fR\*(rq \fIqual qual \fR{\fIqual\fR}) .)l .sp Example: If a user specifies the following clause: .(l not (r.f = 1) or (r.f2 > 1 and 2 > r.f2), .)l then in conjunctive normal form with \*(lqnot\*(rqs removed and variables on the left hand side, we have the following equivalent clause: .(l (r.f != 1 or r.f2 > 1) and (r.f != 1 or r.f2 < 2) .)l In LISP form, it would look like: .(l ((or (!= r.f 1) (> r.f2 1)) (or (!= r.f 1) (< r.f2 2))) .)l .sp A set of macros for manipulating clause entries is contained in: .(l ~postgres/src/planner/clauses.l .)l Additional parse tree manipulation routines are in: .(l ~postgres/src/planner/nodeDefs.l .)l .bp .sh 1 "Query Plan Representation" .sp A query plan is represented as a node. Every plan node contains the following slots: .(l .ft B state qptargetlist lefttree righttree .ft R .)l Thus, while a query plan is externally a single object, it may in fact constitute a tree of plan nodes because of the child tree fields. .sp A \fIplan\fP consists of \fIsubplans\fP interconnected together with \fBRESULT\fR, \fBEXISTENTIAL\fP, and \fBAPPEND\fR nodes. These nodes may also have each other as children. .sp \fBRESULT\fR nodes interconnect plan levels. The planner generates subqueries for all variables which operate at a given level of nesting (that is, all non-nested variables are handled in one plan level, all variables of the form \*(lqfoo.bar.baz\*(rq are handled in another, and so on). Thus, \fBRESULT\fR nodes indicate which attributes should be selected from lower levels in the plan tree. If a \fBRESULT\fR node has subtrees, then the left tree always is a \fIsubplan\fR, and the right tree is a \fIplan\fR for processing the (more deeply nested) remainder of the query. It is also possible for a \fBRESULT\fR node to have only a single left subtree. This occurs when the \fBRESULT\fR node is needed solely for storing relation-level clauses. A query plan can be a single \fBRESULT\fR node with no subtrees if the query contains no variables. .sp \fBEXISTENTIAL\fP nodes also connect subplans. The left subtree of an \fBEXISTENTIAL\fP node is a special subplan which determines whether the existential members of the subplan qualification are all true or not. The right subtree is the actual query plan for the subquery (minus the existential qualification clauses). \fBEXISTENTIAL\fP nodes may also have one (left) or zero subtrees. .sp \fBAPPEND\fR nodes indicate that the executor should use the subplans it contains sequentially, returning the appropriate tuples in a seamless manner (at least as far as the external interface is concerned). \fBAPPEND\fR nodes may be thought of as taking the place of N scan nodes, each of which are substituted for the \fBAPPEND\fR node in turn. .sp A \fIsubplan\fR is an access plan for processing the (current) topmost level of attributes in a query and consists of join and scan nodes. .sp Joins are represented such that the left tree is the outer join relation and the right tree is the inner join relation. The three types of join nodes are: .(l .ft B NESTLOOP MERGESORT HASHJOIN .ft R .)l The two types of scan nodes are: .(l .ft B SEQSCAN INDEXSCAN .ft R .)l .sp Lastly, there are two types of nodes which involve the creation of temporary relations: .(l .ft B SORT HASH .ft R .)l If a stream of tuples must be sorted into a temporary prior to join processing, its parent is a \fBSORT\fR node and the parent of the \fBSORT\fR node is a \fBSEQSCAN\fR node: .(l <some-join> \fB\*(ar SEQSCAN \*(ar SORT \*(ar\fR <some-scan> .)l Similarly, if the relation is to be hashed, its corresponding scan node's parent is a \fBHASH\fR node. .(l <some-join> \fB\*(ar SEQSCAN \*(ar HASH \*(ar\fR <some-scan> .)l Example: A \*(lqretrieve\*(rq involving a single mergesort join that uses an index as an ordered inner path and a sorted outer path might look like: .(l .ft B MERGE \*(ar SEQSCAN \*(ar SORT \*(ar SEQSCAN SORT \*(ar INDEXSCAN .ft R .)l .sp The same idea applies to sorts in general. The node is simply preceded by a \fBSORT\fR and then a \fBSEQSCAN\fR node in the plan tree. However, if a retrieve result is to be sorted into a relation, the \fBSEQSCAN\fR node is omitted. .sp Example: The top level nodes for a plan that returns a set of tuples that must be sorted into a particular order might look like: .(l \fBRESULT \*(ar SORT \*(ar\fR ...rest of plan... .)l .bp .sh 1 "Primitive Nodes" .sp The following is a description of the primitive nodes, which are used in both the input query tree and the final query plan. .sp Each type of node is implemented as a defstruct vector. To access slots within a node, use: .(l (get_\fIslotname node\fR) .)l where \fIslotname\fR is the desired slot name as described in this section and \fInode\fR is an appropriate defstruct node. .sp To set a slot field, use: .(l (set_\fIslotname node new-slot-value\fR) .)l For details see .(l ~postgres/src/planner/nodeDefs.l .)l .sp .sh 2 "RESDOM" .ip "1)" \fBresno\fR - result domain number. This is equivalent to the attribute number for a (temporary or result) tuple. Just as attribute numbers being at 1, a \fBresno\fR of 1 denotes the first attribute in a targetlist. .ip "2)" \fBrestype\fR - either: .br (1) the OID corresponding to the type of the result, or .br (2) *UNION-TYPE-ID*, an identifier for a type internal to the planner that describes multi-dot attributes (since it cannot determine the final attribute type until the nesting is eliminated by the executor). .ip "3)" \fBreslen\fR - length of a domain element in bytes (-1 if it is variable length). .ip "4)" \fBresname\fR - result domain name, either user-specified or the corresponding name of an attribute (if applicable). .ip "5)" \fBreskey\fR - ordinality of the result domain as a sort or hash key, e.g., 0 if the domain won't be included as a sort or hash key; 1 if the domain is the first key, 2 if it is the second, and so on. .ip "6)" \fBreskeyop\fR - OID of the operator on which \fBreskey\fR will be sorted or hashed. .sp .lp To create a \fBRESDOM\fR node: .sp (make_resdom \fIresno restype reslen resname reskey reskeyop\fR) .sp .sh 2 "VAR" .ip "1)" \fBvarno\fR - From the parser's standpoint, \fBvarno\fR is simply the index into the rangetable corresponding to the relation an attribute belongs to. .sp For the query processor, \fBvarno\fR may take on one of three values depending on the attribute entry under consideration. .br (1) If \fBVAR\fR belongs to the relation currently being scanned (either a cataloged or temporary relation, but not a materialized one), \fBvarno\fR is still the \fIindex into the rangetable\fP corresponding to the relation being scanned. .br (2) If \fBVAR\fR is associated with some join node, varno is the \fIname of the temporary join relation\fP accessed. If \fBVAR\fR originates from the outer join relation, \fBvarno\fR = \fB\*(lqOUTER\*(rq\fR. If it originated from the inner join relation, \fBvarno\fR = \fB\*(lqINNER\*(rq\fR. .br (3) For \fBVAR\fRs corresponding to entries within relations that are materialized from a POSTQUEL field or attributes from some previous nesting level, \fBvarno\fR is a \fIreference pair\fP, i.e., a list (\fIlevelnum resno\fR), that corresponds to the attribute entry where either the query field or desired value can be found. \fIlevelnum\fR refers to the processing level number (where \fI0\fR is the topmost), and \fIresno\fR refers to the result domain number within the tuple where the entry is stored. .sp Therefore, whether a relation should be materialized is implicit in the \fBvarno\fR value and information in the attribute entry corresponding to the query field. .ip "2)" \fBvarattno\fR - as with \fBvarno\fR, the meaning of this field depends on the node's position in the plan tree. .br (1) For attributes at the topmost nesting level, \fBvarattno\fR corresponds to the \fIattribute number\fR within a relation (or domain number within a tuple if this is a join tuple \(em that is, if \fBvarno\fR = \fB\*(lqOUTER\*(rq\fR or \fB\*(lqINNER\*(rq\fR). .br (2) If the attribute corresponds to some attribute from a previous nesting level, \fBvarattno\fR = \fInil\fR. .br (3) For nested attributes, the value of \fBvarattno\fR is a \fIstring\fR identical to the attribute name since the attribute number will not be known until the POSTQUEL field is materialized. Note that at the lowest nesting level, \fBvarattno\fR may be \*(lq\fBALL\fR\*(rq (again, since neither the parser nor the planner know what the attributes of the field's parent are \(em it must be determined at run-time by the query processor when the appropriate POSTQUEL field is retrieved). .ip "3)" \fBvartype\fR - either: .br (1) the OID of the type of the attribute referred to by \fBvarattno\fR, or .br (2) *UNION-TYPE-ID* .ip "4)" \fBvardotfields\fR - list of attribute names beyond the first nesting level. .br (\fIThis field is internal to the parser and planner\fR) .ip "5)" \fBvararrayindex\fR - array index of a variable, nil if this is not an array attribute. .br Since arrays can only contain primitive types, only the bottommost attribute in a nesting will be array indexed. The parser will set the \fBvararrayindex\fR field if a variable contains an array index. The planner will only set this field if the query processor is to retrieve an array element within some attribute entry. .ip "6)" \fBvarid\fR - a list containing \fBvarno\fR and \fBvarattno\fR, as well as \fBvardotfields\fR and \fBvararrayindex\fR (if the latter two exist). .br (\fIThis field is internal to the planner\fR) .sp .nf Example: w.x.y.z[a] .sp .nf The parser will set the following fields: .sp \fBvarno\fR = identifier of w, \fBvarattno\fR = attribute number of x, .br \fBvardotfields\fR = (y z), \fBvararrayindex\fR = a, .br \fBvarid\fR = (\fBvarno varattno\fR y z (a)), \fBvartype\fR = type of attribute x .fi .sp .lp To create a \fBVAR\fR node: .sp (make_var \fIvarno varattno vartype vardotfields vararrayindex varid\fR) .sp .sh 2 "OPER" .ip "1)" \fBopno\fR - for the parser, \fBopno\fR is the OID of the operator to which this node corresponds. For the executor, \fBopno\fR is the OID of the operator \fIprocedure\fR. The conversion occurs in the planner (which needs the operator OID to determine selectivities). .ip "2)" \fBoprelationlevel\fR - t if an operator is a relation level operator. .ip "3)" \fBopresulttype\fR - OID of the result type of this particular operator. .sp .lp To create a \fBOPER\fR node: .sp (make_oper \fIopno oprelationlevel opresulttype\fR) .sp .sh 2 "CONST" .ip "1)" \fBconsttype\fR - OID of the constant's type. .ip "2)" \fBconstlen\fR - length in bytes (-1 if it is a variable-length type). .ip "3)" \fBconstvalue\fR - actual value of the constant (i.e., the internal representation). .br \fBconstvalue\fR is nil if the constant is null. Objects represented by pointers must appear as palloc'ed LISP vectori-bytes. .ip "4)" \fBconstisnull\fR - t if the constant has the null value. .br This is set by the planner when filling in \*(lqreplace\*(rq and \*(lqappend\*(rq targetlist entries which are unspecified by the user. If the typdefault field of the \fBTYPE\fR relation is not specified, \fBconstisnull\fR is set to t and \fBconstvalue\fR is set to nil. .sp .lp To create a \fBCONST\fR node: .sp (make_const \fIconsttype constlen constvalue constisnull\fR) .sp .sh 2 "PARAM" .ip "1)" \fBparamid\fR - either: .br (1) a fixnum corresponding to the parameter name for constant value substitution, e.g., \*(lq1\*(rq in the case of \*(lq$1\*(rq .br (2) a string corresponding to the attribute name for relation name substitution, e.g, \*(lqattname\*(rq in the case of \*(lq$.attname\*(rq .sp .lp To create a \fBPARAM\fR node: .sp (make_param \fIparamid\fR) .sp .sh 2 "FUNC" .ip "1)" \fBfuncid\fR - OID of the function to which this node corresponds. .ip "2)" \fBfunctype\fR - OID of the type of the function's return value. .sp .lp To create a \fBFUNC\fR node: .sp (make_func \fIfuncid functype\fR) .bp .sh 1 "Plan Nodes" .sp The following is a description of each type of plan node. Each type of node is implemented as a defstruct vector. To access slots within a node, use: .(l (get_\fIslotname node\fR) .)l where \fIslotname\fR is the desired slot name as described in this section and \fInode\fR is an appropriate defstruct node. .sp To set a slot field, use: .(l (set_\fIslotname node new-slot-value\fR) .)l For details see .(l ~postgres/src/planner/nodeDefs.l .)l .sp .sh 2 "RESULT" .ip "1)" \fBstate\fR - used by the query executor to store runtime-specific information. .ip "2)" \fBqptargetlist\fR - the target list for a sublevel of the query; the attributes in node \fBRESULT\fI(i)\fR are derived from values returned by \fIsubplan(i)\fR, and either \fBRESULT\fI(i+1)\fR or \fIsubplan(i+1)\fR, depending on whether or not there is an i+1'th nesting level. .ip "3)" \fBlefttree\fR - \fIsubplan(i)\fR. .ip "4)" \fBrighttree\fR - either \fBRESULT\fI(i+1)\fR or \fIsubplan(i+1)\fR, depending on whether or not there are deeper nesting levels. .ip "5)" \fBresrellevelqual\fR - list of any relation level clauses that must be satisfied (e.g., \*(lqR1.f1 = R2.f2\*(rq or \*(lqfoo.bar = 2\*(rq) .ip "6)" \fBresconstantqual\fR - a list containing all qualifications which contain no var nodes. .br This field will only be set at the topmost \fBRESULT\fR node. These qualifications should always be tested first at runtime; if they are false, then the rest of the query plan need not be processed because no tuples will be returned. .sp To create a \fBRESULT\fR node: .sp (make_result \fIqptargetlist resrellevelqual lefttree righttree\fR) .sp .sh 2 "EXISTENTIAL" .ip "1)" \fBstate\fR .ip "2)" \fBqptargetlist\fR - always nil. .ip "3)" \fBlefttree\fR - subplan for the existential query. .br This is planned as a \*(lqretrieve\*(rq with a null target list. .ip "4)" \fBrighttree\fR - subplan for the non-existential query. .sp .lp To create a \fBEXISTENTIAL\fR node: .sp (make_existential \fIlefttree righttree\fR) .sp .sh 2 "APPEND" .ip "1)" \fBstate\fR .ip "2) - 4) \fBqptargetlist\fR, \fBlefttree\fR, \fBrighttree\fR - always nil" .ip "5)" \fBplans\fR - a list of plans which are to be executed sequentially. .ip "6)" \fBrelid\fR - the rangetable index of the variable which caused this node to be formed. For example, if this is a query that uses the \fBfrom\fR clause \*(lqfrom p in person*\*(rq, then this would contain the rangetable index of the entry for \*(lqperson\*(rq. .ip "7)" \fBrtentries\fR - a list of rangetable entries which must be substituted into the executor's rangetable in conjunction with execution of the plans stored in the \fBplans\fR field. .ip "8)" \fBflags\fR - a symbol from \fBarchive\fR, \fBinheritance\fR, \fBunion\fR, or \fBversion\fR that specifies how the executor should execute each entry in the \fBplans\fR. .sp .lp To create a \fBAPPEND\fR node: .sp (make_append \fIplans relid rtentries flags\fR) .sp .sh 2 "NESTLOOP" .ip "1)" \fBstate\fR .ip "2)" \fBqptargetlist\fR - attributes to be retrieved into the join result from attributes in the inner and outer join relations. .ip "3)" \fBlefttree\fR - outer join path. .ip "4)" \fBrighttree\fR - inner join path. .ip "5)" \fBqpqual\fR - a list of join clauses to be satisfied. .sp .lp To create a \fBNESTLOOP\fR node: .sp (make_nestloop \fIqptargetlist qpqual lefttree righttree\fR) .sp .sh 2 "HASHJOIN" .ip "1) - 5) from above" .ip "6)" \fBmergehashclauses\fR - join clauses to be used in performing the hash join; if there are multiple clauses, the clauses are arranged in the order of the hash keys, from primary downward. .br Note: These clauses are not contained in \fBqpqual\fR above to avoid redundant checking. .sp .lp To create a \fBHASHJOIN\fR node: .sp (make_hashjoin \fIqptargetlist qpqual mergehashclauses lefttree righttree\fR) .sp .sh 2 "MERGESORT" .ip "1) - 5) from above" .ip "6)" \fBmergehashclauses\fR - join clauses to be used in performing the merge join; if there are multiple clauses, the clauses are arranged in the order of the merge keys, from the primary ordering key downward. .br (Again, these clauses are not contained in \fBqpqual\fR) .ip "7)" \fBmergesortop\fR - OID of the operator procedure used to merge the tuples. .sp .lp To create a \fBMERGESORT\fR node: .sp (make_mergesort \fIqptargetlist qpqual mergehashclauses mergesortop lefttree righttree\fR) .sp .sh 2 "SEQSCAN" .ip "1)" \fBstate\fR .ip "2)" \fBqptargetlist\fR - attributes to be retrieved into scan result. .ip "3)" \fBlefttree\fR - either nil, a \fBSORT\fR node, or a \fBHASH\fR node. .ip "4)" \fBrighttree\fR - always nil. .ip "5)" \fBqpqual\fR - list of restriction clauses on the relation. .ip "6)" \fBscanrelid\fR - either: .br (1) an index into the rangetable corresponding to the relation to be scanned, or .br (2) a reference to an attribute from a previous level that corresponds to a relation to be materialized from some POSTQUEL field. .sp .lp To create a \fBSEQSCAN\fR node: .sp (make_seqscan \fIqptargetlist qpqual scanrelid lefttree\fR) .sp .sh 2 "INDEXSCAN" .ip "1) - 2) from above" .ip "3) - 4) \fBlefttree\fR, \fBrighttree\fR - always nil. .ip "5) - 6) from above" .ip "7)" \fBindxid\fR - list of the OIDs of all indices to be used to scan a relation: (OID1 OID2 ... ). The idea here is that more than one index may be used to scan a relation. For example, if we have the clause \*(lqR.foo = foo or R.foo = foobar\*(rq, the first index might use \*(lqfoo\*(rq as a key and the second could use \*(lqfoobar\*(rq. Currently, this tactic is only used as just described (in conjunction with \*(lqor\*(rq clauses). .ip "8)" \fBindxqual\fR - list of qualifications to be used in conjunction with each index (e.g., ((qual1) (qual2)), where qual1 corresponds to ID1 and qual2 corresponds to ID2). For multi-key indices, subclauses are arranged in the order of the index keys. .br Note, again, that the clauses here are not contained in the \fBqpqual\fR field above to avoid redundant checking. .sp If \fBindxqual\fR is nil, but \fBindxid\fR isn't, then the entire relation is to be scanned starting at the first key of the index. This is used when the ordering of an indexscan is needed for a mergesort. .sp If an index is defined on an inner join relation, \fBindxqual\fR may be a join clause. If this is the case, the query processor must substitute values for the outer relation at runtime. The outer join attribute is identified by its relative position of within the resulting tuple of the outer join relation. This type of qualification is also omitted from \fBqpqual\fR above to avoid redundant checking. .sp .lp To create a \fBINDEXSCAN\fR node: .sp (make_indexscan \fIqptargetlist qpqual scanrelid indxid indxqual\fR) .sp .sh 2 "SORT" .ip "1)" \fBstate\fR .ip "2)" \fBqptargetlist\fR - targetlist for the tuples which are to be placed into the temporary relation. .ip "3)" \fBlefttree\fR - plan node whose result is to be sorted. .ip "4)" \fBrighttree\fR - always nil. .ip "5)" \fBtempid\fR - either: .br (1) a string corresponding to a user-specified result relation, or .br (2) *TEMP-RELATION-ID* (a special identifier indicating a temporary relation). .ip "6)" \fBkeycount\fR - the number of sort keys. .sp .lp To create a \fBSORT\fR node: .sp (make_sort \fIqptargetlist tempid lefttree\fR) .sp .sh 2 "HASH" .ip "1) - 6) from above" .sp 2 .lp To create a \fBHASH\fR node: .sp (make_hash \fIqptargetlist tempid lefttree\fR)